/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
 * 注: 最近公共祖先的定义为: 对于有根树T的两个节点p、q, 最近公共祖先表示为一个节点x，满足x
 * 是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)
*/
/**
 * val: 节点值
*/
function TreeNode (val) {
    this.val = val;
    this.left = this.right = null;
}
/**
 * root: 根节点
 * p: 节点
 * q: 节点
*/
function lowestCommonAncestor (root, p, q) {
    // 如果根节点为null, 则直接返回null
    if (root === null) return null;
    // 遍历到p或者q, 不需要往下遍历
    if (root === p || root === q) return root;
    // 遍历子树
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    // 左子树、右子树都有结果返回root
    if (left && right) {
        return root;
    }
    // 只有其中一个子树有结果
    if (!left) {
        return right;
    }
    if (!right) {
        return left;
    }
}
// 节点
let root = new TreeNode(3);
let node5 = new TreeNode(5);
let node1 = new TreeNode(1);
let node6 = new TreeNode(6);
let node2 = new TreeNode(2);
let node0 = new TreeNode(0);
let node8 = new TreeNode(8);
let node7 = new TreeNode(7);
let node4 = new TreeNode(4);
// 树结构
root.left = node5;
root.right = node1;
node5.left = node6;
node5.right = node2;
node1.left = node0;
node1.right = node8;
node2.left = node7;
node2.right = node4;
console.log(lowestCommonAncestor(root, node5, node4)); // 输出5